/**
 * @param {number[]} nums
 * @return {number}
 */
export var minMoves2 = function (nums) {
  // nums.sort((a, b) => a - b)
  // let mid = nums[Math.floor(nums.length / 2)]
  let mid = quickSelect2(nums, 0, nums.length - 1, nums.length >> 1)
  console.log('mid', mid)
  return nums.reduce((a, b) => a + Math.abs(b - mid), 0)
}

/**
快速选择
*/
function quickSelect2(nums, left, right, k) {
  if (left >= right) return nums[k]
  const m = (left + right) >> 1
  let pivot = nums[m]
  ;[nums[m], nums[left]] = [nums[left], nums[m]]
  let i = left
  let j = right
  while (i < j) {
    while (nums[i] <= pivot && i < right) i++
    while (nums[j] >= pivot && j > left) j--
    if (i < j) [nums[i], nums[j]] = [nums[j], nums[i]]
  }
  ;[nums[left], nums[j]] = [nums[j], nums[left]]
  if (j === k) return nums[k]
  if (j > k) return quickSelect(nums, left, j - 1, k)
  if (j < k) return quickSelect(nums, j + 1, right, k)
}

/**
 * 官方提解所用的快速选择
 * @param {*} nums
 * @param {*} left
 * @param {*} right
 * @param {*} index
 * @returns
 */
const quickSelect = (nums, left, right, index) => {
  const q = randomPartition(nums, left, right)
  if (q === index) {
    return nums[q]
  } else {
    return q < index
      ? quickSelect(nums, q + 1, right, index)
      : quickSelect(nums, left, q - 1, index)
  }
}

const randomPartition = (nums, left, right) => {
  const i = Math.floor(Math.random() * (right - left + 1)) + left
  swap(nums, i, right)
  return partition(nums, left, right)
}

const partition = (nums, left, right) => {
  let x = nums[right],
    i = left - 1
  for (let j = left; j < right; ++j) {
    if (nums[j] <= x) {
      ++i
      swap(nums, i, j)
    }
  }
  swap(nums, i + 1, right)
  return i + 1
}

const swap = (nums, index1, index2) => {
  const temp = nums[index1]
  nums[index1] = nums[index2]
  nums[index2] = temp
}
